    时间复杂度 n方
 ListNode* sortInList(ListNode* head) {
               ListNode* dummy=new ListNode(-1);
        while(head){
            ListNode* p=dummy;
            while(p->next && p->next->val<head->val) p=p->next;    ///之前自己写的是p  不是p->next，调试虽然可以通过，但是有部分不能ac,注意这两种区别 
            ListNode *nextNode=head->next;
            head->next=p->next;
            p->next=head;
            head=nextNode;
        
        }
        return dummy->next;
    }


    时间复杂度  nlogn

    class Solution {
public:
	/**
	 *
	 * @param head ListNode类 the head node
	 * @return ListNode类
	 */
ListNode* sortInList(ListNode* head) {
	// write code here


	if (!head) return nullptr;
	int length = 0;
	ListNode *countNode = head;
	while (countNode)  //计算链表长度
	{
		length++;
		countNode = countNode->next;
	}
	ListNode *dummy = new ListNode(-1);
	dummy->next = head;


	for (int subLen = 1; subLen < length; subLen <<= 1)

	{
		ListNode *pre = dummy;
		ListNode *curr = dummy->next;   ///这里不能写成head->next
		while (curr)  //链未被拆完则继续 按照subLen进行两两合并
		{
			ListNode *head_1 = curr;
			for (int i = 1; i < subLen && curr &&curr->next; i++)
			{
				curr = curr->next;
			}

			ListNode *head_2 = curr->next;
			curr->next = nullptr; //第一次断链
			curr = head_2;

			for (int i = 1; i < subLen && curr&&curr->next; i++)
			{
				curr = curr->next;
			}
			ListNode *mergedNextNode = nullptr;
			if (curr)
			{
		
				mergedNextNode = curr->next; //保存合并之后要指向的next节点信息
				curr->next = nullptr; //第二次断链 放在括号里面

			}
			//		curr->next = nullptr; //第二次断链


			ListNode *mergedNode = mergeTwoLists(head_1, head_2);
			pre->next = mergedNode;
			while (pre->next)   //获取已合并链的最末节点
			{
				pre = pre->next;
			}
			curr = mergedNextNode;//下次要两两合并的起始节点

		}
	}
	return dummy->next;
}
	ListNode* mergeTwoLists(struct ListNode* head1, struct ListNode* head2) {
		ListNode* dummyHead = new ListNode(0);
		ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;
		while (temp1 != nullptr && temp2 != nullptr) {
			if (temp1->val <= temp2->val) {
				temp->next = temp1;
				temp1 = temp1->next;
			}
			else {
				temp->next = temp2;
				temp2 = temp2->next;
			}
			temp = temp->next;
		}
		if (temp1 != nullptr) {
			temp->next = temp1;
		}
		else if (temp2 != nullptr) {
			temp->next = temp2;
		}
		return dummyHead->next;
	}



};